package 递归回溯.二维版;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No417太平洋大西洋水流问题 {

    /**
     * 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。
     * “太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
     * 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
     * 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
     *
     * 提示：
     * 输出坐标的顺序不重要
     * m 和 n 都小于150
     *
     * 示例：
     * 给定下面的 5x5 矩阵:
     *   太平洋 ~   ~   ~   ~   ~
     *        ~  1   2   2   3  (5) *
     *        ~  3   2   3  (4) (4) *
     *        ~  2   4  (5)  3   1  *
     *        ~ (6) (7)  1   4   5  *
     *        ~ (5)  1   1   2   4  *
     *           *   *   *   *   * 大西洋
     * 返回:
     * [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
     */

    private int allLength;
    private int itemLength;
    private int[][] arr;
    //上 右 下 左
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};
    private int[][] result;
    private boolean[][] flag;

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {

        List<List<Integer>> lists=new ArrayList<>();
        if(matrix.length==0){
            return lists;
        }

        this.allLength=matrix.length;
        this.itemLength=matrix[0].length;
        this.arr=matrix;
        this.result=new int[allLength][itemLength];
        this.flag=new boolean[allLength][itemLength];

        /**
         * 每个点都递归遍历一次,可以遍历到边边就返回true,怎么返回两个true呢?
         * 我们从边界开始逆流而上,太平洋流过的点就+1,大西洋流过的点再+1,最后为2的点就是我们的结果
         */

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(i==0&&!flag[i][j]){
                    //上边
                    dfs(i,j);
                }else if(j==0&&!flag[i][j]){
                    //左边
                    dfs(i,j);
                }
            }
        }
        flag=new boolean[allLength][itemLength];
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(j==itemLength-1&&!flag[i][j]){
                    //右边
                    dfs(i,j);
                }else if(i==allLength-1&&!flag[i][j]){
                    //下边
                    dfs(i,j);
                }
            }
        }

        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(result[i][j]==2){
                    lists.add(Arrays.asList(i,j));
                }
            }
        }
        return lists;
    }

    private void dfs(int startX,int startY){
        result[startX][startY]+=1;
        flag[startX][startY]=true;
        int level=arr[startX][startY];
        for (int i = 0; i < 4; i++) {
            int newX=startX+around[i][0];
            int newY=startY+around[i][1];
            if(verifyEdge(newX,newY)&&!flag[newX][newY]
                    &&level<=arr[newX][newY]){
                //不越界&&未探索&&可上去(平级或低级)
                dfs(newX,newY);
            }
        }
    }

    private boolean verifyEdge(int x,int y){
        return x>=0&&x<=allLength-1&&y>=0&&y<=itemLength-1;
    }

    public static void main(String[] args) {
        int[][] arr={{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        No417太平洋大西洋水流问题 n=new No417太平洋大西洋水流问题();
        List<List<Integer>> lists = n.pacificAtlantic(arr);
        System.out.println(JSON.toJSONString(lists));
    }

}
